package 剑指offer;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class p32_III从上到下打印二叉树 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new LinkedList<>();
        if (root==null) {
            return res;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);

        boolean flag=true;//初始化

        while (!queue.isEmpty()) {
            int size=queue.size();

            //List<Integer> tmp=new LinkedList<>();   List接口中没有 头插的方法，因此只能用有该方法的LinkedList作为引用类型
            LinkedList<Integer> tmp=new LinkedList<>();

            for (int i=0;i<size;i++) {
                TreeNode poll = queue.poll();

                if (poll.left!=null) {
                    queue.add(poll.left);
                }
                if (poll.right!=null) {
                    queue.add(poll.right);
                }

                //flag为 true 表示奇数层，false 表示偶数层
                if (flag){
                    //奇数层 从左到右，即进行 尾插
                    tmp.addLast(poll.val);
                }else {
                    //偶数层 从右到左，即进行 头插
                    tmp.addFirst(poll.val);
                }
            }

            res.add(tmp);
            flag=!flag;
        }

        return res;
    }

    public static void main(String[] args) {
//        List<Integer> tmp=new LinkedList<>();
//        tmp.addFirst(1);
//        tmp.addFirst(2);
        LinkedList<Integer> tmp=new LinkedList<>();
        tmp.addFirst(1);
        tmp.addFirst(2);
        System.out.println(tmp);
    }

}
